//
// Created by zyliu on 2020/12/14.
//


#include <cstdlib>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <random>
#include <map>

#include <pthread.h>
#include <unistd.h>

using namespace std;
#define MAX_CARS 1000


typedef unsigned int car_id_t;
typedef enum {
    SOUTH, EAST, NORTH, WEST
} dir_t;
typedef enum {
    a, b, c, d
} cross_quad_t;


const dir_t const_dir[] = {SOUTH, EAST, NORTH, WEST};// 定义方向类型和方向变量（便于用指针访问）
const dir_t left_dir[] = {WEST, SOUTH, EAST, NORTH};// 左侧的方向
const dir_t right_dir[] = {EAST, NORTH, WEST, SOUTH,};// 右侧的方向
const char str_dir[][6] = {"south", "east", "north", "west"};
dir_t current_dir; // 记录正在正在执行的方向


const cross_quad_t dir_quad1[] = {a, b, c, d};// 与方向对应的第1个区域对应
const cross_quad_t dir_quad2[] = {b, c, d, a};// 与方向对应的第2个区域对应
const cross_quad_t left_quad[] = {d, a, b, c};// 一个方向的车通行后，应该signal的车的方向

int empty_dir = 4;// 当前空闲的quad数，为0时死锁发生
int crossing_time = 20000;//一辆车穿过一个quad要0.5秒，总共需要1秒

bool is_deadlock = false;

bool occupied[4] = {false, false, false, false};

pthread_t tids[MAX_CARS]; // one thread per car
pthread_t daemon_thread; // 守护线程

queue<car_id_t> dir_line[4]; // 当前四个方向的等待队列
car_id_t cur_car[4]; // 当前四个方向的车的id


map<int, int> sendMap;

bool get_blocked[4];

/* 以下是 mutex & cond，有一些不空行代表mutex和cond结对使用 */




// 进入路口时使用,填dir_t
pthread_mutex_t from_dir_mutex[4];
pthread_cond_t from_dir_cond[4];

// 在当前车辆在第一个quad时，因为右前方有车需要等待时使用,填dir_t
pthread_mutex_t block_mutex[4];
pthread_cond_t block_cond[4];

// 检测死锁进程使用
pthread_mutex_t deadlock_mutex;
pthread_cond_t deadlock_cond;

pthread_cond_t resolve_cond; // 等待死锁被消除的cond

pthread_mutex_t state_mutex;

pthread_mutex_t occupy_mutex[4]; // 填dir，表示这个dir对应的第一个quad被占据，左车需要让行

// 四个quad的mutex，填cross_quad_t
pthread_mutex_t quad_mutex[4];

pthread_mutex_t give_and_get_mutex[4];//每个方向的车解锁第一个quad并加锁第二个quad时使用，这个操作应该是原子性的


pthread_mutex_t queue_mutex[4];


void init() {
    pthread_cond_init(&deadlock_cond, NULL);
    pthread_cond_init(&resolve_cond, NULL);

    pthread_mutex_init(&state_mutex, NULL);
    pthread_mutex_init(&deadlock_mutex, NULL);

    for (int i = 0; i < 4; i++) {
        pthread_cond_init(&from_dir_cond[i], NULL);
        pthread_cond_init(&block_cond[i], NULL);

        pthread_mutex_init(&quad_mutex[i], NULL);
        pthread_mutex_init(&block_mutex[i], NULL);
        pthread_mutex_init(&from_dir_mutex[i], NULL);
        pthread_mutex_init(&occupy_mutex[i], NULL);
        pthread_mutex_init(&queue_mutex[i], NULL);
        pthread_mutex_init(&give_and_get_mutex[i], NULL);
    }
}

void cross_the_quad(car_id_t car,quad_t q) {
    printf("car %d is crossing %c\n",car,(char)(q+'a'));
    usleep(crossing_time);
}

void push_one_car(dir_t dir, car_id_t cid) {
    pthread_mutex_lock(&queue_mutex[dir]);
    cur_car[dir] = dir_line[dir].front();
    dir_line[dir].pop();
    pthread_cond_signal(&from_dir_cond[dir]);
    sendMap[cur_car[dir]] = cid;
    pthread_mutex_unlock(&queue_mutex[dir]);
}

void push_cars(int push_num = 4) {

    is_deadlock = false;//当处理完最后一辆车，进行push cars的时候，才完全解开死锁

    // 随机产生唤醒方向的顺序
    static vector<dir_t> shuffled_dirs = {NORTH, SOUTH, WEST, EAST};
    random_device rd;
    mt19937 rng(rd());
    shuffle(shuffled_dirs.begin(), shuffled_dirs.end(), rng);

    for (int i = 0; i < push_num; i++) {
        dir_t dir = shuffled_dirs[i];// 当前一轮选中的方向
        if (!dir_line[dir].empty()) {// 这个方向有车在排队
            push_one_car(dir, dir_line[dir].front());
        }

    }
}


void *sched_car_with_dir_param(void *ptr) {
    dir_t this_dir = *(dir_t *) ptr; // 获取当前进程要处理的方位

    // 首先获取方位的准入权
    pthread_mutex_lock(&from_dir_mutex[this_dir]);
    pthread_cond_wait(&from_dir_cond[this_dir], &from_dir_mutex[this_dir]);
    pthread_mutex_unlock(&from_dir_mutex[this_dir]);
    car_id_t car = cur_car[this_dir];


    pthread_mutex_lock(&state_mutex);// 保护状态操作
    current_dir = this_dir;
    printf("car %d from %s is going in %c,which is sent by %d\n", car, str_dir[this_dir], dir_quad1[this_dir] + 'a',
           sendMap[car]);
    if (empty_dir - 1 == 0) {// 要死锁了，就不对第一个quad加锁了
        printf("deadlock detected!here car is %d\n", car, sendMap[car]);
        is_deadlock = true;
        pthread_mutex_unlock(&state_mutex);
        pthread_cond_signal(&deadlock_cond); // 唤醒死锁进程
        pthread_cond_wait(&resolve_cond, &quad_mutex[dir_quad1[this_dir]]);// 用自己持有的quad1的锁去等待被揭开
        printf("deadlock resolved\n");
        // resolve被signal后就是解决死锁了
        // 自己开出去的代码
        cross_the_quad(car,dir_quad1[this_dir]);

        // 锁2让1，更新状态时要锁住
        pthread_mutex_lock(&state_mutex);
        pthread_mutex_lock(&quad_mutex[dir_quad2[this_dir]]);
        pthread_mutex_unlock(&quad_mutex[dir_quad1[this_dir]]);
        occupied[this_dir] = false;
        pthread_mutex_unlock(&state_mutex);

        cross_the_quad(car,dir_quad2[this_dir]);

        printf("car %d from %s is leaving the crossing1\n", car, str_dir[this_dir]);
        pthread_mutex_unlock(&quad_mutex[dir_quad2[this_dir]]);
        printf("the empty is %d\n", empty_dir);
        is_deadlock = false;
        push_cars();

        return NULL;

    } else {// 不死锁才加锁

        if (pthread_mutex_trylock(&quad_mutex[dir_quad1[this_dir]]) == EBUSY) {
            // 没获取到锁，此处添加一些处理？
            pthread_mutex_unlock(&state_mutex);// 第一次没获取到锁，这个时候先把state解锁，防止死锁
            pthread_mutex_lock(&quad_mutex[dir_quad1[this_dir]]);
            pthread_mutex_lock(&state_mutex);
        }

        occupied[this_dir] = true;
        empty_dir--;
        printf("car %d from %s has got in %c,which is sent by %d\n", car, str_dir[this_dir], dir_quad1[this_dir] + 'a',
               sendMap[car]);
        pthread_mutex_unlock(&state_mutex);
    }

    cross_the_quad(car,dir_quad1[this_dir]);// 没死锁，就先开到路中间，准备进入第二个quad
    get_blocked[this_dir] = false;// 记录是否被右前方车block住
    pthread_mutex_lock(&state_mutex);
    if (occupied[right_dir[this_dir]]) {// 右前方有车挡住了
        get_blocked[this_dir] = true;
        printf("here,car is %d from %s is waiting for its right car:%d\n", car, str_dir[this_dir],
               cur_car[right_dir[this_dir]]);
        pthread_mutex_unlock(&state_mutex);


        // 等待右前方把自己signal
        pthread_mutex_lock(&block_mutex[this_dir]);
        pthread_cond_wait(&block_cond[this_dir], &block_mutex[this_dir]);
        pthread_mutex_unlock(&block_mutex[this_dir]);
        printf("car %d is released\n", car);
        // 当被signal且死锁的时候，它必然至少是第二个死锁被放的车，所以此时is_deadlock必定为真
        if (is_deadlock) {// 死锁了，但必然不是自己造成的，就走过去，把自己右边的车叫醒就行

            cross_the_quad(car,dir_quad1[this_dir]);//这时，它先走到路中间，而不是在出发点等右前方车，否则会导致饥饿

            /** 有可能死锁
            //锁2放1,死锁状态下就不考虑occupied了
            pthread_mutex_lock(&quad_mutex[dir_quad2[this_dir]]);
            pthread_mutex_unlock(&quad_mutex[dir_quad2[this_dir]]);
             */

            pthread_mutex_lock(&state_mutex);
            //锁2放1,死锁状态下就不考虑occupied了
            pthread_mutex_lock(&quad_mutex[dir_quad2[this_dir]]);
            pthread_mutex_unlock(&quad_mutex[dir_quad1[this_dir]]);
            empty_dir++;
            if (current_dir == left_dir[this_dir]) {// 如果左边的车导致死锁，就解开了死锁
                pthread_cond_signal(&resolve_cond);
            } else {// 如果不是，传递解开的链条，让左车走，直到出现第一种情况
                pthread_cond_signal(&block_cond[left_dir[this_dir]]);
            }
            pthread_mutex_unlock(&state_mutex);
            cross_the_quad(car,dir_quad2[this_dir]);
            pthread_mutex_lock(&state_mutex);
            occupied[this_dir] = false;
            pthread_mutex_unlock(&quad_mutex[dir_quad2[this_dir]]);
            pthread_mutex_unlock(&state_mutex);
            printf("car %d from %s is leaving the crossing2\n", car, str_dir[this_dir]);
            return NULL;
        }
    } else {
        pthread_mutex_unlock(&state_mutex);
    }

    // 苦苦等到右前方没车了,可以过去了
    pthread_mutex_lock(&state_mutex);
    // 这个时候锁必然获取的到，因为后面只有左边没车的时候，才会放同方向的车出来，而放出来的时候这个锁已经被获取到了
    pthread_mutex_lock(&quad_mutex[dir_quad2[this_dir]]);
    pthread_mutex_unlock(&quad_mutex[dir_quad1[this_dir]]);
    empty_dir++;
    occupied[this_dir] = false;
    pthread_mutex_unlock(&state_mutex);

    cross_the_quad(car,dir_quad2[this_dir]);

    pthread_mutex_unlock(&quad_mutex[dir_quad2[this_dir]]);
    printf("car %d from %s is leaving the crossing3,empty quad:%d\n", car, str_dir[this_dir], empty_dir);

    // 容易遗漏的一步
    // 当前的车要走的时候，事实上让出了右前方车道面前的格子
    // 如果没有这一步，右前方方向的车就只可能在push_cars的时候才能开（starvation）
    // 如果它放在后面的，当前方向的signal之后，就破坏了规则
    // 因为当前方向要让行右前方，不能先signal
    if (!dir_line[right_dir[this_dir]].empty() && !is_deadlock && get_blocked[this_dir]) {

        push_one_car(right_dir[this_dir], car);
    }

    if (is_deadlock) {

        pthread_mutex_lock(&state_mutex);
        if (current_dir == left_dir[this_dir]) {// 如果左边的车导致死锁，就解开了死锁
            printf("Ended! left is %s,current is %s\n", str_dir[left_dir[this_dir]], str_dir[current_dir]);
            pthread_cond_signal(&resolve_cond);
        } else {// 如果不是，传递解开的链条，让左车走，直到出现第一种情况
            printf("Not ended!left is %s,current is %s\n", str_dir[left_dir[this_dir]], str_dir[this_dir]);
            pthread_cond_signal(&block_cond[left_dir[this_dir]]);
        }
        pthread_mutex_unlock(&state_mutex);

    } else {
        pthread_mutex_lock(&state_mutex);

        if (occupied[left_dir[this_dir]] && get_blocked[left_dir[this_dir]]) {// 如果左边有车等着，让左边的车先过
            pthread_cond_signal(&block_cond[left_dir[this_dir]]);
            printf("tested left but not self,%d\n",car);

        } else {
            if (!dir_line[this_dir].empty()) {// 判断过了左边的，才轮到自己这边，下次通过上一个if让自己这边signal
                push_one_car(this_dir, car);
            }
        }
        pthread_mutex_unlock(&state_mutex);
    }

    return NULL;
}


void *run_daemon(void *ptr) {
    printf("here at daemon\n");

    push_cars(); // 初始的push cars,启动




}


int main() {


    char *cars = new char[MAX_CARS];
    cin >> cars;// 应该使用小写字符
    int i = 0;

    init();


    for (; i < strlen(cars); ++i) {
        switch (cars[i]) {
            case 'n':
                dir_line[NORTH].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[NORTH]);
                break;
            case 's':
                dir_line[SOUTH].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[SOUTH]);
                break;
            case 'w':
                dir_line[WEST].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[WEST]);
                break;
            case 'e':
                dir_line[EAST].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[EAST]);
                break;

        }
    }
    push_cars();
//    pthread_create(&daemon_thread, NULL, run_daemon, NULL);// 这个死锁检测线程是守护线程，车处理完了就可以退出
    for (i = 0; i < strlen(cars); ++i) {
        pthread_join(tids[i], NULL);
    }
    printf("\nend\n");


}